import sun.reflect.generics.tree.Tree;

import java.lang.reflect.Array;
import java.util.*;

public class binaryTree {
    /**
     * 二叉树的层序遍历
     */
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        Queue<TreeNode> queue = new LinkedList<>();
        ArrayList<Integer> result = new ArrayList<>();

        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode father = queue.poll();
            result.add(father.val);
            if (father.left != null) {
                queue.offer(father.left);
            }
            if (father.right != null) {
                queue.offer(father.right);
            }
        }
        return result;
    }

    /**
     * 输入一个非空整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果.
     * 如果是则输出Yes,否则输出No.假设输入的数组的任意两个数字都互不相同
     *
     * 思路:
     * 二叉搜索树:或者是一棵空树,或者具有下列性质的二叉树:若他的左子树不为空,则左子树上的所有节点的值
     * 均小于他的根节点的值;若他的右子树不为空,则右子树上所有节点的值均大于他的根节点的值
     *
     */
    public boolean VerifySquenceOfBST(int [] sequence) {
          if (sequence == null || sequence.length == 0) {
              return false;
          }
          return VerifySquenceOfBSTHelper(sequence,0,sequence.length-1);
    }

    private boolean VerifySquenceOfBSTHelper(int[] sequence, int start, int end) {
        if (start >= end) {
            //在不断查找过程中,区域不断缩小,为空时,证明之前的所有范围都满足检测条件
            //也就是 是一个BST
            return true;
        }
        //拿到root的值
        int root = sequence[end];
        //先遍历左半部分,也就是整体都要比root小,拿到左子树序列
        int i = start;
        while (i < end && sequence[i] < root) {
            i++;
        }
        //再检测右子树是否符合大于root的条件,要从i 开始,也就是右半部分的开始
        for (int j = i;j < end;j++) {
            if (sequence[j] < root) {
                return false;
            }
        }
        //走到这里,就说明,当前序列满足需求,但不代表题目被解决了,还要在检测left和right各自是否也满足
        return VerifySquenceOfBSTHelper(sequence,start,i-1) &&
                VerifySquenceOfBSTHelper(sequence,i,end-1);
    }

    /**
     * 输入一棵二叉树的根节点和一个整数,打印出二叉树中的节点值的和为输入整数的所有路径
     * 路径定义为从树的根节点开始往下一直到叶结点所经过的节点形成一条路径
     * 回溯法:
     * 1.先添加值 (待选结果)
     * 2.在判定现有结果是否满足条件(待选结果是否符合条件)
     * 3.DFS(深度优先)
     * 4.回退(检测下一个)
     *
     */
    /**
     * 回溯法:基于二叉,多叉树的穷举过程,在穷举的过程汇总,要进行剪枝
     */
    public void FindPathDFS(TreeNode root,int target,
                            ArrayList<ArrayList<Integer>> result,ArrayList<Integer> list) {

        if (root == null) {
            return;
        }
        //将当前值放入list待选结果中
        list.add(root.val);
        //更新目标值
        target -= root.val;
        //1.已经是叶子节点了
        //2.从root到该叶子节点,之和是target
        //3.是叶子节点,但是不满足节点,也不影响,程序会直接退出
        if (root.left == null && root.right == null && target == 0) {
            //回溯剪枝,去掉不满足条件的结果
            result.add(new ArrayList<Integer>(list));//注意深浅拷贝
        }
        FindPathDFS(root.left,target,result,list);//DFS递归统计
        FindPathDFS(root.right,target,result,list);

        list.remove(list.size() - 1);
    }
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> list = new ArrayList<>();
        FindPathDFS(root,target,result,list);
        return result;
    }
    /**
     * 输入一个字符串,按字典序打印出该字符串的所有排列
     * 例如输入字符串abc ,则打印出由字符串a,b,c所能排列出来的所有字符串abc,acb,bac,cab和cba
     * 解题思路：
     * 全排列问题，可以看做如下多叉树形态
     *  ________________ 开始 _______________
     *         /        |         \
     *  ____ a ____ ___ b ___ ___ c ___ -> 第一阶段
     *      / \        / \       / \
     *     b  c       a   c     a   b -> 第二阶段
     *     |  |       |   |     |   |
     *     c  b       c   a     b   a -> 第三阶段
     * 很明显,我们想要得到合适的排列组合,一定是深度优先的
     * 该问题可以把目标串理解成两部分:第一部分:以哪个字符开头,第二部分:剩下的是子问题
     * 所以,我们要让每个字符串都要做一遍开头,然后在求解子问题
     *
     * 1.穷举所有可能性
     * 2.根据特定条件,进行去掉不满足的
     * 3.排列是这棵多叉树的路径
     */
    public ArrayList<String> Permutation(String str) {

        ArrayList<String> result = new ArrayList<>();
        if (str != null && str.length() > 0) {
            PermutationHelper(str.toCharArray(),0,result);
            Collections.sort(result);
        }
        return result;
    }

    private void PermutationHelper(char[] str, int start, ArrayList<String> result) {
        if (start == str.length-1) {
            if (!isExist(result,str)) {
                result.add(new String(str));
            }
            return;
        }
        for (int i = start;i < str.length;i++) {
            swap(str,start,i);
            PermutationHelper(str,start+1,result);
            swap(str,start,i);
        }
    }

    private void swap(char[] str, int start, int end) {
        char temp = str[start];
        str[start] = str[end];
        str[end] = temp;
    }

    private boolean isExist(ArrayList<String> result, char[] str) {
        return result.contains(String.valueOf(str));
    }

    /**
     * 输入一棵二叉树，求该树的深度。
     * 从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径
     * 的长度为树的深度
     */
    public int TreeDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(TreeDepth(root.left),TreeDepth(root.right));

    }
    /**
     * 二叉树的镜像
     */
    public TreeNode Mirror(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        Mirror(root.left);
        Mirror(root.right);
        return root;
    }
    /**
     * 对称二叉树
     */
    boolean recursion(TreeNode root1,TreeNode root2) {
        //两边都为空
        if (root1 == null && root2 == null) {
            return true;
        }
        //一边为空或者值不相同
        if (root1 == null || root2 == null || root1.val != root2.val) {
            return false;
        }
        return recursion(root1.left,root2.right) && recursion(root1.right,root2.left);
    }
    boolean isSymmetrical(TreeNode pRoot) {
        return recursion(pRoot,pRoot);
    }
    /**
     * 判断是不是平衡二叉树
     */
    public boolean IsBalancedTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        //调用二叉树的深度
        int left = TreeDepth(root.left);
        int right = TreeDepth(root.right);
        if (left - right > 1 || left - right < -1) {
            return false;
        }
        return IsBalancedTree(root.left) && IsBalancedTree(root.right);
    }
    /**
     * 给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。
     * 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示
     */
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
                int n = pre.length;
                int m = vin.length;
                //每个遍历都不能为0
                if(n == 0 || m == 0)
                    return null;
                //构建根节点
                TreeNode root = new TreeNode(pre[0]);
                for(int i = 0; i < vin.length; i++){
                    //找到中序遍历中的前序第一个元素
                    if(pre[0] == vin[i]){
                        //构建左子树
                        root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1),
                                Arrays.copyOfRange(vin, 0, i));
                        //构建右子树
                        root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length),
                                Arrays.copyOfRange(vin, i + 1, vin.length));
                        break;
                    }
                }
                return root;
    }
    /**
     * 给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回
     */
    public class TreeLinkNode {
        int val;
        TreeLinkNode left = null;
        TreeLinkNode right = null;
        TreeLinkNode next = null;

        TreeLinkNode(int val) {
            this.val = val;
        }
    }
    //1.首先根据当前给出的节点找到根节点
    //2.然后根节点调用中序遍历
    //3.将中序遍历结果存储
    //4.最终拿当前节点匹配是否有符合要求的下一个节点
    ArrayList<TreeLinkNode> nodes = new ArrayList<>();
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        TreeLinkNode root = pNode;
        //获取根节点
        while(root != null) {
            root = root.next;
        }
        //中序遍历打造nodes
        InOrder(root);
        //进行匹配
        int n = nodes.size();
        for (int i = 0; i < n-1; i++) {
            TreeLinkNode cur = nodes.get(i);
            if (pNode == cur) {
                return nodes.get(i+1);
            }
        }
        return null;
    }
    public void InOrder(TreeLinkNode root) {
        if(root != null) {
            InOrder(root.left);
            nodes.add(root);
            InOrder(root.right);
        }
    }
    /**
     * 给定一棵结点数为n 二叉搜索树，请找出其中的第 k 小的TreeNode结点值。
     * 1.返回第k小的节点值即可
     * 2.不能查找的情况，如二叉树为空，则返回-1，或者k大于n等等，也返回-1
     * 3.保证n个节点的值不一样
     */
    //step 1：设置全局变量count记录遍历了多少个节点，res记录第k个节点。
    //step 2：另写一函数进行递归中序遍历，当节点为空或者超过k时，结束递归，返回。
    //step 3：优先访问左子树，再访问根节点，访问时统计数字，等于k则找到。
    //step 4：最后访问右子树

    //记录返回的节点
    public TreeNode res = null;
    //记录中序遍历了多少个
    public int count = 0;
    public void midOrder(TreeNode root, int k) {
        //当遍历到节点为空或者超过k时，返回
        if (root == null || count > k) {
            return;
        }
       midOrder(root.left,k);
        count++;
        //只记录第k个
        if (count == k) {
            res = root;
        }
        midOrder(root.right,k);

    }
    public int KthNode (TreeNode proot, int k) {
        midOrder(proot,k);
        if (res != null) {
            return res.val;
        }else {
            return -1;
        }
    }

    /**
     * 树的子结构 :
     * 输入两棵二叉树A，B，判断B是不是A的子结构。（我们约定空树不是任意一个树的子结构）
     */
    public static boolean HasSubtree(TreeNode root1, TreeNode root2) {
        boolean result = false;
        //当Tree1和Tree2都不为零的时候，才进行比较。否则直接返回false
        if (root2 != null && root1 != null) {
            //如果找到了对应Tree2的根节点的点
            if(root1.val == root2.val){
                //以这个根节点为为起点判断是否包含Tree2
                result = doesTree1HaveTree2(root1,root2);
            }
            //如果找不到，那么就再去root的左儿子当作起点，去判断时候包含Tree2
            if (!result) {
                result = HasSubtree(root1.left,root2);
            }

            //如果还找不到，那么就再去root的右儿子当作起点，去判断时候包含Tree2
            if (!result) {
                result = HasSubtree(root1.right,root2);
            }
        }
        //返回结果
        return result;
    }

    public static boolean doesTree1HaveTree2(TreeNode node1, TreeNode node2) {
        //如果Tree2已经遍历完了都能对应的上，返回true
        if (node2 == null) {
            return true;
        }
        //如果Tree2还没有遍历完，Tree1却遍历完了。返回false
        if (node1 == null) {
            return false;
        }
        //如果其中有一个点没有对应上，返回false
        if (node1.val != node2.val) {
            return false;
        }
        //如果根节点对应的上，那么就分别去子节点里面匹配
        return doesTree1HaveTree2(node1.left,node2.left) && doesTree1HaveTree2(node1.right,node2.right);
    }

    /**
     * 从上到下打印二叉树,空节点不打印
     */
    public ArrayList<Integer> PrintFromTopToBottom1(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        //队列存储
        Queue<TreeNode> q = new ArrayDeque<TreeNode>();
        q.offer(root);
        while (!q.isEmpty()) {
            TreeNode cur = q.poll();
            res.add(cur.val);
            if (cur.left != null) {
                q.add(cur.left);
            }
            if (cur.right != null) {
                q.add(cur.right);
            }
        }
        return res;
    }
    /**
     * 二叉搜索树与双向链表
     * 输入一个二叉搜索树, 将其变为排序的双向链表
     */
    TreeNode pre = null;
    TreeNode root = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }
        //递归遍历左子树
        Convert(pRootOfTree.left);
        //判断特殊情况
        if (root == null) {
            root = pRootOfTree;
        }
        //修改遍历的节点为双向链表
        if (pre != null) {
            pRootOfTree.left = pre;
            pre.right = pRootOfTree;
        }
        //更新节点
        pre = pRootOfTree;
        //递归遍历右子树
        Convert(pRootOfTree.right);
        return root;
    }
    /**
     * 找到二叉树的最近公共祖先
     * 给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。
     */
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        return helper(root,o1,o2).val;
    }

    private TreeNode helper(TreeNode root, int o1, int o2) {
        if (root == null || root.val == o1 || root.val == o2) {
            return root;
        }
        TreeNode left = helper(root.left,o1,o2);
        TreeNode right = helper(root.right,o1,o2);
        //如果left为空,说明这两个节点在root节点的右子树上,只需要返回右子树查找的结果即可
        if (left == null) {
            return right;
        }
        //如果right为空,同上
        if (right == null) {
            return left;
        }
        //如果left和right都不为空,说明这两个节点一个在root的左子树上一个在右子树上
        //只需要返回cur节点即可
        return root;
    }
    /**
     * 按之字形 打印二叉树
     * 给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
     */
    public ArrayList<ArrayList<Integer> > PrintZhi(TreeNode pRoot) {
        return null;
    }
    /**
     * 把二叉树打印成多行
     * 给定一个节点数为 n 二叉树，要求从上到下按层打印二叉树的 val 值，
     * 同一层结点从左至右输出，每一层输出一行，将输出的结果存放到一个二维数组中返回。
     */
    ArrayList<ArrayList<Integer>> PrintHang(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if (pRoot == null) {
            return res;
        }
        //队列每次只保存当前层的节点
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(pRoot);

        while (!queue.isEmpty()) {
            ArrayList<Integer> list = new ArrayList<>();
            //le 为每一层左边节点的指针,ri 为右边节点指针
            int le = 0,ri = queue.size();
            //从左到右按顺序遍历当前层的每一个结点
            while (le++ < ri) {
                TreeNode node = queue.poll();
                //收集当前层每一个结点的值
                if (node != null) {
                    list.add(node.val);
                }
                //按顺序加入左右子结点,为下一层遍历做准备
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            //收集当前层的结果
            res.add(list);
        }
        return res;
    }


}







